package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.IntegerUtils;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/maximum-swap/?envType=daily-question&envId=2024-01-22">最大交换</a><br/>
 *      给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。<br/>
 *      给定数字的范围是 [0, 10^8]<br/>
 *      例: <br/>
 *          输入: 2736<br/>
 *          输出: 7236<br/>
 *          解释: 交换数字2和数字7。<br/>
 * </p>
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/22 15:31
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode670 {

    /**
     * <p>
     *     最大交换
     * </p>
     */
    public static  int maximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int n = charArray.length;
        int maxNum = num;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(charArray, i, j);
                maxNum = Math.max(maxNum, Integer.parseInt(new String(charArray)));
                swap(charArray, i, j);
            }
        }
        return maxNum;
    }

    public static void swap(char[] charArray, int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }


    /**
     * <p>
     *     最大交换
     * </p>
     */
    public static int checkMaximumSwap(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int leftIndex = -1;
        int rightIndex = -1;
        int maxIndex = charArray.length - 1;
        int maxVal = charArray[charArray.length - 1];
        for (int i = charArray.length - 1; i >= 0; i--) {
            if (charArray[i] > maxVal) {
                maxVal = charArray[i];
                maxIndex = i;
            } else if (charArray[i] < maxVal) {
                leftIndex = i;
                rightIndex = maxIndex;
            }
        }
        if (leftIndex == -1) return num;
        char leftChar = charArray[leftIndex];
        charArray[leftIndex] = charArray[rightIndex];
        charArray[rightIndex] = leftChar;
        return Integer.valueOf(String.valueOf(charArray));
    }

    public static void main(String[] args) {
        int maxVal = 10^8;
        int testTimes = 10000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            Integer val = IntegerUtils.generateRandomInteger(maxVal);
            if (maximumSwap(maxVal) != checkMaximumSwap(maxVal)) {
                System.out.println("Oops!");
                System.out.println(maxVal);
                break;
            }
        }
        System.out.println("Test End!");
    }
}
